package tom.change.回溯算法.八皇后问题;

//起始行为0
public class ChessBoard {

	//皇后的数量，改成属性是为了方便扩展
	private Integer EmpressCount;
	//用来存储放置皇后的位置(map[i]=j表示在第i行第j列放置皇后)
	private Integer[] map;
	//解的个数 用于统计
	private Integer sum;
	//初始化皇后类
	public ChessBoard(Integer count){
		sum=0;
		this.EmpressCount=count;
		map=new Integer[this.EmpressCount];
		for(int i=0;i<this.EmpressCount;i++){
			map[i]=0;
		}
	}

	//判断该位置是否符合要求
	public boolean isLawful(Integer x){
		boolean flag=true;
		//遍历已经在棋盘上的皇后确定当前皇后的位置是否合法
		for(int i=0;i<x;i++){
			if(map[i]==map[x]||(Math.abs(i-x)==Math.abs(map[i]-map[x]))){
				//在同一行 或者 同一列 或者斜对角线    -----不合法
				flag=false;
				break;
			}
		}
		return flag;
	}
	
	//遍历map地图，放置皇后  index 是放置的皇后序号，一开始是0
	public void start(Integer index){
		if(index==this.EmpressCount){
			//放置完成
			sum++;
			for(int i=0;i<this.EmpressCount;i++){
				//打印皇后的位置
				System.out.println(i+1+"行"+(map[i]+1)+"列");
			}
			System.out.println("***********************line***********************");
		}else {
			//未到达根节点
			//遍历列数
			for(int j=0;j<this.EmpressCount;j++){
				//将第index个皇后放置在第index行第j列
				map[index]=j;
				//将放置的皇后进行位置判断
				if(isLawful(index)){
					//合法，继续下一个
					start(index+1);
				}else {
					//不合法，继续下一列  这里不做任何操作，仅为方便阅读
				}
			}
			//for循环结束没有找到合适的，自然回溯到上一行继续上一行的下一列
		}
	}
	
	//获取解的个数
	public Integer getSum(){
		return sum;
	}
}
